package com.fe.class03;

import java.util.Arrays;

/**
 * @Description 用递归方法求数组中的最大值
 * 形如
 * T(N) = a T(N/b) + O(N^d)(其中的a、b、d都是常数)
 * 的递归函数，可以直接通过Master公式来确定时间复杂度
 * 如果 log(b,a) < d，复杂度为O(N^d)
 * 如果 log(b,a) > d，复杂度为O(N^log(b,a))
 * 如果 log(b,a) == d，复杂度为O(N^d logN)
 * master公式要求每个部分的复杂度一致才可以求解, 复杂度不一致无法使用
 * @Author sosuke :-)
 * @Date 2021/12/12 18:35
 */
public class Code10_GetMax {

    public static Integer getMax(int[] arr) {
        if (null == arr || arr.length == 0) {
            return null;
        }
        return process(arr, 0, arr.length - 1);
    }

    /**
     * 使用递归方式实现求数组L...R范围的最大值
     * 大问题可以拆成同等结构的子问题，多个小问题解决以后再整合成一个返回
     * T(N) = 2 * T(N/2) + O(1)
     *      = O(N)
      */
    private static int process(int[] arr, int L, int R) {
        if (L > R) {
            throw new RuntimeException("参数错误");
        }
        // base case，只有一个数，直接返回
        if (L == R) {
            return arr[L];
        }
        // L...R不止一个数
        int mid = L + ((R - L) >> 1);
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

    public static void main(String[] args) {
        int testTimes = 10000;
        int maxSize = 100;
        int maxValue = 200;
        for (int i = 0; i < testTimes; i++) {
            int[] arr = generateRandomArray(maxSize, maxValue);
            // System.out.println(Arrays.toString(arr));
            Integer res1 = getMax(arr);
            Integer res2 = Arrays.stream(arr).boxed().max(Integer::compareTo).orElse(null);
            if (!isEqual(res1, res2)) {
                System.out.println("Fuck");
                System.out.println(Arrays.toString(arr));
                System.out.println("res1 = " + res1);
                System.out.println("res2 = " + res2);
                return;
            }
        }
        System.out.println("Nice");
        int[] arr = generateRandomArray(maxSize, maxValue);
        int res1 = getMax(arr);
        int res2 = Arrays.stream(arr).max().getAsInt();
        System.out.println(Arrays.toString(arr));
        System.out.println("res1 = " + res1);
        System.out.println("res2 = " + res2);
    }

    private static int[] generateRandomArray(int maxSize, int maxValue) {
        int size = (int) (Math.random() * (maxSize + 1));
        int[] arr = new int[size];
        for (int i = 0; i < arr.length; i++) {
            int num = (int) (Math.random() * (maxValue + 1)) - (int) (Math.random() * (maxValue + 1));
            arr[i] = num;
        }
        return arr;
    }

    private static boolean isEqual(Integer o1, Integer o2) {
        if (null == o1 && null != o2) return false;
        if (null != o1 && null == o2) return false;
        if (null == o1) return true;
        return o1.equals(o2);
    }

}
